#include <inttypes.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#include "src/ltlog.h"
#include "src/ltutil.h"

static inline void
Append(uint64_t* array, size_t* i, uint64_t x) {
    array[*i] = x;
    *i += 1;
}

int
main(void) {
    /*
    g(0) = 1
 
    定义：

        m2(k) = min{ t: g(k) <= g(t) * 2 }

    也就是满足 g(k) <= g(t) * 2 的最小的 t。
  
    因为m2(k)=k时，条件一定成立，所以m2必然存在。同理定义m3和m5。
  
        g(k) <= g(m2(k)) * 2
        g(k) <= g(m3(k)) * 3
        g(k) <= g(m5(k)) * 5
  
    这3个不等式至少有一个取等号。这是因为：

        g(k)/2
        g(k)/3
        g(k)/5
  
    之中至少有一个丑数。例如g(k)/2是丑数，那么g(k)/2等于g(m2(k))，则第一个不等
    式取等号。

    根据这个条件，只需要求出m2、m3、m5并在上面不等式右边三项取最小值就可以算出
    g(k)。

    思考m2(k+1)和m2(k)的关系。关键在于g(m2(k)) * 2和g(k)是否相等，

    如果：

        g(k) = g(m2(k)) * 2

    那么：
        => g(k+1) > g(m2(k)) * 2
        => m2(k+1) > m2(k)
        => m2(k+1) >= m2(k) + 1

    另外 g(m2(k)+1) * 2 是一个丑数，而且它大于 g(k) 所以 g(k+1) 小于等于它。

        g(k+1) <= g(m2(k)+1) * 2

    也就得到 m2(k+1) <= m2(k) + 1

    所以 m2(k+1) = m2(k) + 1。

    如果：

        g(k) < g(m2(k)) * 2

    那么因为 g(m2(k)) * 2 是丑数，它不会小于 g(k+1)。

        g(k+1) <= g(m2(k)) * 2

    这就表示 m2(k+1) = m2(k)。

    总之：

        m2(k+1) = case
            m2(k) * 2 == g(k) -> m2(k) + 1
            else              -> m2(k)
        end

    这些式子对m3和m5都成立，就不再重复了。
    */

    static uint64_t u[65536];
    size_t i = 0;

    size_t m2 = 0;
    size_t m3 = 0;
    size_t m5 = 0;

    uint64_t u2;
    uint64_t u3;
    uint64_t u5;

    Append(u, &i, 1);
    for (;;) {
        uint64_t next = ltutil_Min3_U64(u2 = u[m2] * 2, u3 = u[m3] * 3,
                                        u5 = u[m5] * 5);

        Append(u, &i, next);

        ltlog_Log2(Info, "find ugly number", "index:", U64(i - 1),
                   "number:", U64(next));
        if (next > INT64_MAX)
            break;

        m2 += (next == u2) ? 1 : 0;
        m3 += (next == u3) ? 1 : 0;
        m5 += (next == u5) ? 1 : 0;
    }

    return 0;
}
